package com.leetcode.no107;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }

        Queue<TreeNode> nodeQue = new LinkedList<>();
        nodeQue.offer(root);

        while(!nodeQue.isEmpty()){
            List<Integer> tmpList = new ArrayList<>();

            // 取出该层的
            int tmpLen = nodeQue.size();

            while (tmpLen >= 1){
                TreeNode tmpNode = nodeQue.poll();
                tmpList.add(tmpNode.val);
                tmpLen --;

                if(tmpNode.left != null){
                    nodeQue.offer(tmpNode.left);
                }
                if(tmpNode.right != null){
                    nodeQue.offer(tmpNode.right);
                }
            }
            res.add(tmpList);
        }
        Collections.reverse(res);
        return res;
    }
}
